package lc5

/*
 * @lc app=leetcode.cn id=5 lang=golang
 *
 * [5] 最长回文子串
 1 <= s.length <= 1000
 s 仅由数字和英文字母组成
*/

// @lc code=start
func longestPalindrome(s string) string {
	return longestPalindromeDP(s)
}

// 暴力破解优化 O(n³）
func longestPalindromeN3(s string) string {
	result := ""
	for i := 0; i < len(s); i++ {
		for j := i + 1 + len(result); j <= len(s); j++ {
			if isPalindrome(s[i:j]) {
				result = s[i:j]
			}
		}
	}
	return result
}

func isPalindrome(s string) bool {
	length := len(s)
	for i := 0; i < length/2; i++ {
		if s[i] != s[length-1-i] {
			return false
		}
	}
	return true
}

// 动态规划，主要参考是 db[i][j] = db[i+1][j-1]，填写数组的左上部分，可以看官网视频
// 动态规划的入门题，当然这道题目的最优解是马拉车算法
// https://leetcode.cn/problems/longest-palindromic-substring/solution/zui-chang-hui-wen-zi-chuan-by-leetcode-solution/
func longestPalindromeDP(s string) string {
	if len(s) < 2 {
		return s
	}
	var db = make([][]bool, len(s))
	for i := range db {
		db[i] = make([]bool, len(s))
	}
	beg := 0
	maxLen := 0
	for j := 0; j < len(s); j++ {
		for i := 0; i <= j; i++ {
			if s[i] != s[j] {
				db[i][j] = false
				continue
			}
			if (j-1)-(i+1)+1 < 2 {
				db[i][j] = true
			} else {
				db[i][j] = db[i+1][j-1]
			}
			if db[i][j] && j-i+1 > maxLen {
				maxLen = j - i + 1
				beg = i
			}
		}
	}
	return s[beg : beg+maxLen]
}

// @lc code=end
